package 栈和队列;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

//public class MyStack {
//    //两个Queue实现
//    Queue<Integer> queue1; // 和栈中保持一样元素的队列
//    Queue<Integer> queue2; // 辅助队列
//    public MyStack() {
//        queue1 = new LinkedList<>();
//        queue2 = new LinkedList<>();
//    }
//
//    public void push(int x) {
//        queue2.add(x);
//        while(!queue1.isEmpty()){
//            queue2.add(queue1.remove());
//        }
//        Queue<Integer> tempQueue = null;
//        tempQueue = queue1;
//        queue1 = queue2;
//        queue2 = tempQueue;
//    }
//
//    public int pop() {
//        return queue1.remove();
//    }
//
//    public int top() {
//        return queue1.peek();
//    }
//
//    public boolean empty() {
//        return queue1.isEmpty();
//    }
//}

//public class MyStack {
//    // Deque 接口继承了 Queue 接口
//    // 所以 Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirst
//    Deque<Integer> que1; // 和栈中保持一样元素的队列
//    Deque<Integer> que2; // 辅助队列
//    /** Initialize your data structure here. */
//    public MyStack() {
//        que1 = new ArrayDeque<>();
//        que2 = new ArrayDeque<>();
//    }
//
//    /** Push element x onto stack. */
//    public void push(int x) {
//        que1.addLast(x);
//    }
//
//    /** Removes the element on top of the stack and returns that element. */
//    public int pop() {
//        int size = que1.size();
//        size--;
//        // 将 que1 导入 que2 ，但留下最后一个值
//        while (size-- > 0) {
//            que2.addLast(que1.peekFirst());
//            que1.pollFirst();
//        }
//
//        int res = que1.pollFirst();
//        // 将 que2 对象的引用赋给了 que1 ，此时 que1，que2 指向同一个队列
//        que1 = que2;
//        // 如果直接操作 que2，que1 也会受到影响，所以为 que2 分配一个新的空间
//        que2 = new ArrayDeque<>();
//        return res;
//    }
//
//    /** Get the top element. */
//    public int top() {
//        return que1.peekLast();
//    }
//
//    /** Returns whether the stack is empty. */
//    public boolean empty() {
//        return que1.isEmpty();
//    }
//}

public class MyStack {
    // Deque 接口继承了 Queue 接口
    // 所以 Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirst
    Deque<Integer> que1;
    /** Initialize your data structure here. */
    public MyStack() {
        que1 = new ArrayDeque<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        que1.addLast(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int size = que1.size();
        size--;
        // 将 que1 导入 que2 ，但留下最后一个值
        while (size-- > 0) {
            que1.addLast(que1.peekFirst());
            que1.pollFirst();
        }

        int res = que1.pollFirst();
        return res;
    }

    /** Get the top element. */
    public int top() {
        return que1.peekLast();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return que1.isEmpty();
    }
}